/*
 * @Author: szx
 * @Date: 2022-05-08 14:54:57
 * @LastEditTime: 2022-05-08 15:06:04
 * @Description:
 * @FilePath: \leetcode\剑指offerII\118\118.js
 */

var findRedundantConnection = function (edges) {
    const n = edges.length,
        parent = new Array(n + 1).fill(0).map((_, index) => index);
    const find = (index) => (parent[index] === index ? index : find(parent[index]));
    const union = (index1, index2) => (parent[find(index1)] = find(index2));
    for (let i = 0; i < n; i++) {
        const edge = edges[i],
            node1 = edge[0],
            node2 = edge[1];
        if (find(node1) != find(node2)) union(node1, node2);
        else return edge;
    }
    return [0];
};
